package com.gitee.feizns.explore.data_structure.union_find;

/**
 * @author feizns
 * @since 2020/3/11
 */
public class UnionFindPathCompression implements UnionFind {

    private int[] parents;
    private int[] ranks;

    public UnionFindPathCompression(int size) {
        this.parents = new int[size];
        this.ranks = new int[size];
        for (int i = 0; i < size; i++)
            parents[i] = i;
    }

    @Override
    public int size() {
        return parents.length;
    }

    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    @Override
    public void union(int p, int q) {
        int pr = find(p);
        int qr = find(q);
        if ( pr != qr ) {
            if ( ranks[pr] < ranks[qr] )
                parents[pr] = qr;
            else if ( ranks[pr] > ranks[qr] )
                parents[qr] = pr;
            else {
                parents[pr] = qr;
                ranks[qr]++;
            }
        }
    }

    private int find(int p) {
        int r = p;
        while ( r != parents[r] ) {
            parents[r] = parents[parents[r]];
            r = parents[r];
        }
        return r;
    }

    public static void main(String[] args) {
        UnionFind ou = new UnionFindPathCompression(20);
        ou.union(1, 19);
        ou.union(0, 1);

        ou.union(19, 10);
        System.out.println(ou.isConnected(10, 19));
        System.out.println(ou.isConnected(1, 2));
    }

}
